/*
 * @Author: Starfish_DL
 * @Date: 2020-09-19 11:37:26
 * @LastEditTime: 2020-09-23 13:39:48
 * @LastEditors: Starfish_DL
 * @Description: Finish homework of 0917 using C++.
 * @FilePath: \undefinedc:\vscode\cpp\0919.cpp
 */

#include<iostream>
using namespace std;

class iNode
{
public:
    int data;
    iNode* next;
    iNode();
    ~iNode();
};

iNode::iNode()
{
    data=0;
    next=nullptr;
}

iNode::~iNode()
{
}

class iLinkList
{
public:
    iNode *L;

    iLinkList(iNode *&L,int a[],int n); //CreateList();
    iLinkList(int a[],int n); //CreateList();
    ~iLinkList(); //DeleteList();
    bool isListEmpty();
    int ListLength();
    void DispList();
    int GetElem(int n);
    int LocateElem(int e);
    void ListInsert(int e,int n);
    void ListDelete(int n);
    void sort();
};

iLinkList::iLinkList(iNode *&Li,int a[],int n)
{
    //Establishing linked list by tail-inserting method.
    L=Li;
    iNode *p=L,*s;
    for (int i = 0; i < n; i++)
    {
        s=new iNode();
        s->data=a[i];
        p->next=s;
        p=s;
    }
}

iLinkList::iLinkList(int a[],int n)
{
    //Establishing linked list by tail-inserting method.
    L=new iNode();
    iNode *p=L,*s;
    for (int i = 0; i < n; i++)
    {
        s=new iNode();
        s->data=a[i];
        p->next=s;
        p=s;
    }
}

iLinkList::~iLinkList()
{
    iNode *p=L,*pre=L->next;
    while (pre!=nullptr)
    {
        delete p;
        p=pre;
        pre=pre->next;
    }
    delete p;
}

bool iLinkList::isListEmpty()
{
    return (L->next==nullptr);
}

void iLinkList::DispList()
{
    iNode *p=L->next;
    while (p!=nullptr)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
}

int iLinkList::GetElem(int n)
{
    //When the function is wrong, the return value is -1.
    if (n<=0)
    {
        return -1;
    }
    iNode *p=L;
    int k=0;
    while (p!=nullptr && k<n)
    {
        p=p->next;
        k++;
    }
    if (p==nullptr)
    {
        return -1;
    }
    return p->data;
}

int iLinkList::ListLength()
{
    int k=0;
    iNode *p=L->next;
    while (p!=nullptr)
    {
        p=p->next;
        k++;
    }
    return k;
}

void iLinkList::ListDelete(int n)
{
    if (n<=0)
    {
        return;
    }
    iNode *p=L,*s;
    for (int i = 0; i < n-1; i++)
    {
        if (p->next==nullptr)
        {
            return;
        }
        p=p->next;
    }
    s=p->next;
    p->next=s->next;
    delete s;
}

void iLinkList::ListInsert(int e,int n)
{
    if (n<=0)
    {
        return;
    }
    iNode *p=L;
    for (int i = 0; i < n-1; i++)
    {
        if (p->next==nullptr)
        {
            return;
        }
        p=p->next;
    }
    iNode *s=new iNode();
    s->data=e;
    s->next=p->next;
    p->next=s;
}

int iLinkList::LocateElem(int e)
{
    /**
     * @description: If the execution of this function is wrong, return -1,
     * Return the FIRST result of the parameter e;
     * @param {type} 
     * @return {type} 
     */
    iNode *p=L->next;
    int k=1;
    while (p!=nullptr)
    {
        if (e==p->data)
        {
            return k;
        }
        p=p->next;
        k++;
    }
    return -1;
}

void iLinkList::sort()
{
    iNode *p,*pre,*q;
    p=L->next->next;
    L->next->next=nullptr;
    while (p!=nullptr)
    {
        q=p->next;
        pre=L;
        while (pre->next!=nullptr && pre->next->data<p->data)
        {
            pre=pre->next;
        }
        p->next=pre->next;
        pre->next=p;
        p=q;
    }
}

iNode* split_01(iLinkList *Li,int n)
{
    // textbook page52 T2.6
    if (n<=0 || n>=Li->ListLength())
    {
        return nullptr;
    }
    iNode *s=new iNode();
    iNode *p=Li->L;
    for (int i = 0; i < n; i++)
    {
        p=p->next;
    }
    s->next=p->next;
    p->next=nullptr;
    return s;
}

void split_02(iLinkList *Li,iNode *&L1,iNode *&L2)
{
    // textbook page52 T2.6
    L1=Li->L;
    iNode *p=L1->next,*r1=L1,*q;
    while (p!=nullptr)
    {
        r1->next=p;
        r1=p;
        p=p->next;
        q=p->next;
        p->next=L2->next;
        L2->next=p;
        p=q;
    }
    r1->next=nullptr;
}

void delmaxnode(iNode *L)
{
    // textbook page52 T2.7
    iNode *p=L->next,*pre=L,*maxpre=L;
    while (p!=nullptr)
    {
        if (p->data>maxpre->data)
        {
            maxpre->data=p->data;
            maxpre->next=pre->next;
        }
        p=p->next;
        pre=pre->next;
    }
    p=maxpre->next;
    maxpre->next=p->next;
    delete p;
}

void DispList(iNode *L)
{
    iNode *p=L->next;
    while (p!=nullptr)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}

int main(/* int argc, const char** argv */) 
{
    int a[8]={1,2,3,3,4,5,6,7};
    iLinkList *link1=new iLinkList(a,8);
    cout<<link1->LocateElem(4)<<endl;
    // link1->ListInsert(8,5);
    // link1->ListDelete(5);
    // cout<<link1->isListEmpty()<<endl;
    link1->DispList();
    delete link1;
    return 0;
}